Lambda the Ultimate

There's been a lot of activity with Javascript generators lately, with project such as Google Web Toolkit or Links. haXe is an OO language with high-level features (polymorphism, type inference, structural subtyping, iterators) meant to program the Web. It targets three platforms : Javascript, Neko (for the server side) and Flash.

Instead of taking an approach to isolate a "common feature set", haXe has a common standard library but also give access to each platform "native" library. Some classes can be supported on several platforms by using conditional-compilation with platform-specific code. For example haXe includes some optional libraries that can be used for example to do transparent synchronous or asynchronous communications between the platforms (called Remoting).

haXe 1.0 was released a few days ago on http://haxe.org. The haXe compiler is entirely written in OCaml.

Orca (an open-source Rebol-like language) has been chosen as the default scripting language for the Syllable operating system, according to "The Rebol Week" site -
http://rebolweek.blogspot.com/

There have been attempts at creating open-source Rebol-like languages in the past - most notably, Freebell and R-sharp. However, both of those projects have been dormant/dead for some time.

Those interested in trying out Orca can find it here -
http://sourceforge.net/projects/urlan

To build it, you will need "m2", available here -

http://wsrebol.sourceforge.net

Orca now looks like it will become the most successful and most widely-used of the open-source Rebol-like languages. Good luck to its developer ("wickedsmoke") and the Syllable team!

Continuations and MicroThreads on Mono is a modification of the Mono VM to implement...Continuations and MicroThreads!

Consider the following Haskell-ish functions: (I'm not actually gonna type them into hugs or anything so forgive any syntactical errors)

naiveMin [x]  = x
naiveMin x:xs = if x < y then x else y where y = naiveMin xs

qsort []   = []
qsort x:xs = qsort [ a | a <- xs, a < x] ++ [x] ++ qsort [ b | b <- xs, b >= x ]

lazyMin xs = head (take 1 (qsort xs))

Now what I'm asking is, if we have lazy evaluation semantics, in the lazyMin function, when we call qsort, will the only part that gets evaluated be

qsort [ a | a <- xs, a < x]

or possibly at most:

qsort [ a | a <- xs, a < x] ++ [x]

since we are only taking 1 element from the list. Does this mean it's runtime is O(n), like naiveMin? Are we using lazy evaluation to complete change how much code gets run from outside the function? I'm guessing the answer is probably yes, which also kind of turned on the light-bulb as far as the usefulness of lazy evaluation goes. (Oh yeah you can have an infinite list, but um, so what?). I just want to make sure I'm not missing anything here.

From the abstract:

When programmers develop and evolve software, they frequently copy and paste (C&P) code from an existing code base, or sources such as web pages or documentation. We believe that programmers follow a small number of well defined C&P usage patterns when they program, and understanding these patterns would enable us to design tools to improve the quality of software.

I noticed this paper in the references of a (draft) paper on subtext, which is a project previously discussed on LtU. I think that this is interesting from a language design perspective and couldn't find a previous discussion on LtU. (I'll defer my other comments (read: critique) to a later post - if any.)

Google has released a new web toolkit. The possible significant item for LtU is the Java-to-Javascript compiler that is one of the central components of the toolkit. I am unconvinced of the value of coding in java rather than in javascript. However, the marketing folks have been thinking along the same lines as some of the threads here on LtU with respect to static type checking, code completion, etc. Maybe some of the static fans could comment on this?

cheers,
Jess

O’Reilly author chromatic has a string of blog posts describing his maintainable language. Possibly interesting even while it might be an Avril joke? (Didn't notice this posted on LTU yet.)

Lee, E.A., "The Problem With Threads", IEEE Computer, vol. 36, no. 5, May 2006, pp. 33-42, available online as U.C. Berkeley EECS Department Technical Report UCB/EECS-2006-1

For concurrent programming to become mainstream, we must discard threads as a programming model. Nondeterminism should be judiciously and carefully introduced where needed, and it should be explicit in programs.

Many of the points about concurrency raised in this article will be familiar to LtU readers, particularly those who have any familiarity with CTM, but the article does provide a good summary of the issues. Beyond that, what I found interesting (especially from a PLT perspective) is Lee's contention that the emphasis on developing general-purpose languages that support concurrency is misplaced. Lee believes that a better approach is to develop what he calls "coordination languages", which focus on arranging sequential components written in conventional languages into some concurrent configuration (I suppose that piping in a Unix shell could be considered a limited coordination language). Quoting from the article:

"Coordination languages do introduce new syntax, but that syntax serves purposes that are orthogonal to those of established programming languages. Whereas a general-purpose concurrent language like Erlang or Ada has to include syntax for mundane operations such as arithmetic expressions, a coordination language need not specify anything more than coordination. Given this, the syntax can be noticeably distinct."

It's not immediately obvious to me that there's anything preventing a "coordination language" from being a well-defined subset of some more general language. Lee's key point seems to involve making coordination constructs syntactically distinct (e.g. block diagrams vs. text). Which, of course, raises some interesting questions about whether other important facets of a language (such as the language of type declarations) should also have strongly syntactically-distinct representations, and just how homogeneous (Lisp anyone?) the syntax of a language should be...

Ruby and python have been mentioned many times on LtU, but I would like the opinnion of gurus here. Which language is more interesting for those who have deeper knowledge of programming language theory?

I'm not so concerned with speed of respective VMs, the community around these languages, even their syntax, etc. I'm iterested in the languages (and their APIs I suppose).

For example, for practical programming, are ruby's continuations significantly better than python's co-routines (2.5)? How do 'lambda' functions in each language compare?

Is one language closer to 'functional' programming than another? Is one language better than another for building logic programming or constraint logic programming constructs? Is one language better than another for building the kind of functionality found in concurrent languages (erlang, Oz)?

Those following my posts, may know that I am recently enamored with stack-based functional languages (like Joy). I have posted the powerpoint slides from a proposed talk about the Cat Programming Language at http://www.cdiggins.com/cat.ppt.

Here is the proposal which accompanies the presentation:

Cat Programming Language: A Functional Optimization Framework for the MSIL

Abstract

Cat is a stack-based pure functional language, inspired by the Joy programming language, which targets the Microsoft Intermediate Language (MSIL). Cat, like Joy, differs from mainstream functional languages in that it is based on the composition of functions rather than the application of functions. This design makes algebraic manipulation of programs trivial, and thus facilitates optimization.

This goal of the presentation (http://www.cdiggins.com/cat.ppt ) is to introduce the semantics and syntax of Cat, demonstrate rewriting rules for high-level functional optimizations, and show preliminary performance results for a simple IL Code generator written in C#.

Summary of Language

The Cat language is a pure functional language, inspired by Joy, which in turn is inspired by Forth and FP. All constructs in Cat (atomic programs, user defined programs, operators, literals, lists) behave as functions which takes a single stack as input and returns a new stack. In Cat the concatenation of two functions (e.g. [f g]) has the effect of composition of both functions (e.g. g(f(x))). All new user defined functions are defined as lists of functions. Cat not only has no variable declaration, there are no argument declarations. Cat also lends itself to the higher order functional programming: the lambda operation in Cat is the list construction operator "[...]" and currying can be achieved used basic operations such as "cons".

Results of Research

The primary result of the work done with Cat is the observation that high-level functional optimizations can be very easily expressed and applied. Consider the examples:

f map g map => [f g] map
[f] map x [g] fold => x [[f' f] g] fold 
[f] filter x [g] fold => x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold => x [f g [h] [pop] if] fold 

These optimizations are very important, but are extremely hard to apply once a langauge has been reduced to an assembly, or pseudo-assembly, form.

The thesis of this work is that by first compiling a language to a stack-based functional language such as Cat, before targeting a lower level target such as MSIL, better performance can be achieved.